home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / glass / glass.lha / GLASS / glammar / gg07.c < prev    next >
C/C++ Source or Header  |  1991-01-21  |  16KB  |  563 lines
  1. /*
  2.  
  3.     This file is a part of the GLAMMAR source distribution 
  4.     and therefore subjected to the copy notice below. 
  5.     
  6.     Copyright (C) 1989,1990  Eric Voss, ericv@cs.kun.nl 
  7.  
  8.     This program is free software; you can redistribute it and/or modify
  9.     it under the terms of the GNU General Public License as published by
  10.     the Free Software Foundation version 1
  11.  
  12.     This program is distributed in the hope that it will be useful,
  13.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.     GNU General Public License for more details.
  16.  
  17.     You should have received a copy of the GNU General Public License
  18.     along with this program; if not, write to the Free Software
  19.     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20. */
  21. /* file: lattices */
  22. #include "gg1.h"
  23. #include "gg2.h"
  24.  
  25. int group = 0, count,top, unique_lattice_count=0, prev_group = -1;
  26. char  repr_group[1000][6], *lattice_substitution_name,*lattice_val_repr;
  27. int max_group,prev_mem;
  28. static int lline;
  29. static int lat_error = 0;
  30.  
  31. set_lattice_groups() {
  32.   int ag;
  33.   for (ag = first_lattice; ag != nil; ag = BROTHER(ag)) {
  34.     if (DEF(ag) == -1) {
  35.       count = 0;
  36.       DEF(ag) = group;
  37.       top = ag;
  38.       (void) sprintf(repr_group[group],"%d",group);
  39.       set_group(ag);
  40.       group += 1;
  41.     }
  42.   }
  43.   max_group = group;
  44. /*  fprintf (stderr,"%d lattice catogories\n",group); */
  45. }
  46.  
  47.  
  48. set_group(ag)
  49. int ag;
  50. {
  51.   int mem = SON(ag);
  52.   if (REPR(mem) == REPR(ag)) {
  53.       NODENAME(mem) =  1 << count++;
  54.       NODENAME(ag) =  NODENAME(mem);
  55.       DEF(mem) =  -1;
  56.       if (count > 30) {
  57.         fprintf(stderr, "lattice rule %s: to much elements (>31)", REPR(ag));
  58.         exit(1);
  59.       }
  60.      return;
  61.   } 
  62.   for (mem = SON(ag) ; mem != nil; mem = BROTHER(mem)) {
  63.     int def  = DEF(mem);
  64.     if ( def == -1) 
  65.        set_mem_lattice(mem);
  66.     else if (DEF(def) == -1) {
  67.       DEF(def) = group;
  68.       set_group(def);
  69.     }
  70.     else if (DEF(def) != group)  {
  71.       fprintf(stderr, "lattice rule %s used in different groups\n",REPR(mem));
  72.       exit(1);
  73.     }
  74.   }
  75.   NODENAME(ag) = 0;
  76.   for (mem = SON(ag) ; mem != nil; mem = BROTHER(mem)) 
  77.     if (DEF(mem) == -1) 
  78.       NODENAME(ag) |= NODENAME(mem);
  79.     else 
  80.       NODENAME(ag) |= NODENAME(DEF(mem));
  81.  
  82. }
  83.  
  84. set_mem_lattice(mem)
  85. {
  86.    register int    ag,member;
  87.    register char * repr = REPR(mem);
  88.    for (ag = top;  ag != nil; ag = BROTHER(ag))
  89.       for (member = SON(ag); member != nil; member = BROTHER(member))  
  90.           if (mem == member){
  91.              NODENAME(mem) =  1 << count++;
  92.              if (count > 30) {
  93.                fprintf(stderr, "lattice rule %s: to much elements (>31)",
  94.                             REPR(ag));
  95.                exit(1);
  96.              }
  97.              return;
  98.            } else if (REPR(member) == repr) {
  99.               NODENAME(mem) = NODENAME(member);
  100.               return;
  101.            }
  102. }               
  103. link_lattice()
  104. {
  105.    register int    ag,member;
  106.  
  107.    for (ag = first_lattice; ag != nil; ag = BROTHER(ag))
  108.       for (member = SON(ag); member != nil; member = BROTHER(member))  {
  109.          register int r_ag = first_lattice;
  110.          while (REPR(member) != REPR(r_ag)) {
  111.             if (r_ag == nil)  {
  112.                DEF(member) = -1;
  113.                break;
  114.             } else
  115.                r_ag = BROTHER(r_ag);
  116.          }
  117.          if (r_ag != nil)  
  118.                DEF(member) = r_ag;
  119.       }
  120.    set_lattice_groups();
  121. }
  122.  
  123.  
  124. lattice_defined(rule,alt,trm)
  125. int alt,trm;
  126. {
  127.    register int    ag,l;
  128.    for (ag = first_lattice; ag != nil; ag = BROTHER(ag))
  129.       if (REPR(trm) == REPR(ag))  {
  130.          LATTICE_DEF(trm) = ag;
  131.          return;
  132.       }
  133.    l = LINE(alt);
  134.    if (separate_comp_flag)
  135.       fprintf(stderr,"In %s:\n",PART(rule));
  136.    if (first_lattice != nil)  {
  137.       fprintf(stderr,"line %d: LATTICE affix %s not defined\n",l,REPR(trm));
  138.       fprintf(stderr,"line %d, affix %s: FLOW SYMBOL expected\n",l,REPR(trm));
  139.    } else  
  140.       fprintf(stderr,"line %d,affix %s: FLOW SYMBOL expected\n",l,REPR(trm));
  141.    exit(1);
  142. }
  143.  
  144.  
  145. tr_lattice() {
  146.   register int ag,mem, afx,alt,rule;
  147.   if (lat_trad_flag)  {
  148.        transformlattice = tltraditional;
  149.        transformlatticeterm = tltraditionalterm;
  150.   }
  151.   for (rule = root; rule != laststdpred; rule = BROTHER(rule)) {
  152.     lline = LINE(SON(rule));
  153.     for (alt = SON (rule) ; alt != nil; alt = BROTHER (alt)) {
  154.       for (afx = AFFIXDEF (alt) ; afx != nil; afx = BROTHER (afx))
  155.         if (LATTICE(afx) ) 
  156.           if (defining_occurence_of_lattice_affix(REPR(SON(afx)),SON(alt)))
  157.              tr_lattice_to_afx(SON(afx),alt,SON(alt));
  158.           else 
  159.              tr_lattice_term_to_afx(SON(afx),alt,SON(alt));
  160.       for (mem = SON (alt) ; mem != nil; mem = BROTHER (mem))
  161.        if (DEF(mem) != transformlattice)
  162.         for (afx = AFFIXTREE (mem) ; afx != nil; afx = BROTHER (afx))
  163.               if (LATTICE(afx) ) 
  164.                 tr_lattice_to_afx(SON(afx),alt,mem);
  165.     }
  166.   }
  167.  if (lat_error>0)  exit(1);
  168. }
  169. int defining_occurence_of_lattice_affix(repr,mem) 
  170. char * repr;
  171. int mem;
  172. {    
  173.       int afx;
  174.       for (; mem != nil; mem = BROTHER (mem))
  175.         for (afx = AFFIXTREE (mem) ; afx != nil; afx = BROTHER (afx))
  176.            if ((LATTICE(afx)) && (repr == REPR(SON(afx))))
  177.                return true;
  178.       return false;
  179. } 
  180.  
  181. int done;
  182.  
  183. tr_lattice_term_to_afx(trm,alt,member)
  184. int trm,alt,member;
  185. {
  186.       register int afx,mem, term;
  187.       register char * repr = REPR(LATTICE_DEF(trm));
  188.       int lat_val = NODENAME(LATTICE_DEF(trm));
  189.       
  190.  
  191.       group = DEF(LATTICE_DEF(trm)); 
  192.       lattice_substitution_name = &chartable[++charindex];
  193.       (void) sprintf(&chartable[charindex], "T_%d", unique_lattice_count++);
  194.       charindex += 10;
  195.       if (charindex > maxchars) 
  196.            alloc_chartable();
  197.       lattice_val_repr = &chartable[++charindex];
  198.       (void) sprintf(&chartable[charindex], "%d", lat_val);
  199.       charindex += 20;
  200.       if (charindex > maxchars) 
  201.            alloc_chartable();
  202.  
  203.       done = false;
  204.       for (afx = AFFIXDEF (alt) ; afx != nil; afx = BROTHER (afx))
  205.         if (!LATTICE(afx) ) 
  206.           for (term = SON (afx); term != nil; term = BROTHER (term))
  207.              if (repr == REPR(term)) {
  208.                if (!done) {
  209.                   done = true;
  210.                   add_lattice_term_to_afx_node(term,alt);
  211.                }
  212.                else 
  213.                  REPR(term) = lattice_substitution_name; 
  214.              }
  215.       prev_mem = nil;
  216.       for (mem = SON (alt);mem != nil; prev_mem = mem,mem = BROTHER (mem))
  217.        if (DEF(mem) != transformlattice)
  218.         for (afx = AFFIXTREE (mem) ; afx != nil; afx = BROTHER (afx))
  219.           if (!LATTICE(afx) )
  220.             for (term = SON (afx); term != nil; term = BROTHER (term))
  221.              if (repr == REPR(term)) {
  222.                if (!done) {
  223.                   done = true;
  224.                   insert_lattice_term_to_afx_node(term,mem,alt);
  225.                   check_used_before_defined(mem,member,alt,repr); 
  226.                }
  227.                else 
  228.                  REPR(term) = lattice_substitution_name;
  229.              }
  230. }
  231.  
  232. tr_lattice_to_afx(trm,alt,member)
  233. int trm,alt,member;
  234. {
  235.       register int afx,mem, term;
  236.       register char * repr = REPR(LATTICE_DEF(trm));
  237.  
  238.       group = DEF(LATTICE_DEF(trm)); 
  239.       lattice_substitution_name = &chartable[++charindex];
  240.       (void) sprintf(&chartable[charindex], "T_%d", unique_lattice_count++);
  241.       charindex += 10;
  242.       if (charindex > maxchars) 
  243.            alloc_chartable();
  244.       done = false;
  245.       for (afx = AFFIXDEF (alt) ; afx != nil; afx = BROTHER (afx))
  246.         if (!LATTICE(afx) ) 
  247.           for (term = SON (afx); term != nil; term = BROTHER (term))
  248.              if (repr == REPR(term)) {
  249.                if (!done) {
  250.                   done = true;
  251.                   add_lattice_to_afx_node(repr,term,alt);
  252.                }
  253.                else 
  254.                  REPR(term) = lattice_substitution_name; 
  255.              }
  256.       prev_mem = nil;
  257.       for (mem = SON (alt);mem != nil; prev_mem = mem,mem = BROTHER (mem))
  258.        if (DEF(mem) != transformlattice)
  259.         for (afx = AFFIXTREE (mem) ; afx != nil; afx = BROTHER (afx))
  260.           if (!LATTICE(afx) )
  261.             for (term = SON (afx); term != nil; term = BROTHER (term))
  262.              if (repr == REPR(term)) {
  263.                if (!done) {
  264.                   done = true;
  265.                   if (DERIVED(afx))
  266.                      append_lattice_to_afx_node(trm,term,mem);
  267.                   else    
  268.                      insert_lattice_to_afx_node(trm,term,mem,alt);
  269.                   check_used_before_defined(mem,member,alt,repr); 
  270.                }
  271.                else 
  272.                  REPR(term) = lattice_substitution_name;
  273.              }
  274. }
  275.  
  276. check_used_before_defined(use_mem,def_mem,alt,repr) 
  277. int use_mem,def_mem,alt;
  278. char *repr;
  279. {
  280.  int mem ;
  281.  for (mem = SON(alt); (mem != nil) && (def_mem != mem); mem = BROTHER(mem)) 
  282.    if (use_mem == mem) {
  283.      fprintf(stderr, 
  284. "line %d in %s: cannot delay evaluation of lattice term '%s' (defined at '%s')\n",
  285.         lline,REPR(use_mem),repr,REPR(def_mem));
  286.       lat_error +=1;
  287.    }
  288. }
  289. /*  
  290.  *  add node "transform  lattice (>group,>LATTICE, T_%d.>).
  291.  */
  292.  
  293. add_lattice_to_afx_node(lattice,term,alt)
  294. int  term, alt;
  295. char *lattice;
  296. {
  297.    int b,mem ;
  298. /*  T_%d> */
  299.    REPR(term) = lattice_substitution_name;
  300.    newnode(affixnt, nil, nil, lattice_substitution_name);
  301.    newnode(derived, nil, brother, "(nil)");
  302.    b = brother;
  303. /*  LATTICE */
  304.    newnode(affixnt, nil, nil, lattice);
  305.    newnode(inherited, b,brother, "(nil)");
  306.    b = brother;
  307. /*  >"groupnr" */
  308.    newnode(affixtm,  nil, nil, repr_group[group]);
  309.    newnode(inherited, b, brother, "(nil)");
  310.  
  311. /*  transform lattice */
  312.    newdefnode(ntnode, nil, brother, transformlattice, 
  313.                    REPR(transformlattice));
  314.  
  315.  mem = SON(alt);
  316.  if (mem  == nil) {
  317.       SON(alt) = brother;
  318.       return;
  319.  }
  320.  for  (; BROTHER(mem) != nil; mem = BROTHER(mem));
  321.  BROTHER (mem) = brother;
  322. }
  323.  
  324. /*  
  325.  *  append  node "transform  lattice (>group,LATTICE, T_%d.>).
  326.      after mem
  327.  */
  328.  
  329. append_lattice_to_afx_node(lattice,term,mem)
  330. int lattice,term, mem;
  331. {
  332.    int b ;
  333.    REPR(term) = lattice_substitution_name;
  334.  
  335. /*  T_%d> */
  336.    newnode(affixnt, nil, nil, lattice_substitution_name);
  337.    newnode(derived, nil, brother, "(nil)");
  338.    b = brother;
  339. /*  LATTICE */
  340.    newnode(affixnt, nil, nil, REPR(lattice));
  341.    newnode(inherited, b,brother, "(nil)");
  342.    b = brother;
  343. /*  >"groupnr" */
  344.    newnode(affixtm,  nil, nil, repr_group[group]);
  345.    newnode(inherited, b, brother, "(nil)");
  346.  
  347. /*  transform lattice */
  348.    newdefnode(ntnode, nil, brother, transformlattice, 
  349.                    REPR(transformlattice));
  350.    b = BROTHER(mem);
  351.    BROTHER (mem) = brother;
  352.    BROTHER (brother) = b;
  353.  
  354. }
  355.  
  356. insert_lattice_to_afx_node(lattice,term,mem,alt)
  357. int lattice,term, mem;
  358. {
  359.    int b ;
  360.    REPR(term) = lattice_substitution_name;
  361.  
  362. /*  T_%d> */
  363.    newnode(affixnt, nil, nil, lattice_substitution_name);
  364.    newnode(derived, nil, brother, "(nil)");
  365.    b = brother;
  366. /*  LATTICE */
  367.    newnode(affixnt, nil, nil, REPR(lattice));
  368.    newnode(inherited, b,brother, "(nil)");
  369.    b = brother;
  370. /*  >"groupnr" */
  371.    newnode(affixtm,  nil, nil, repr_group[group]);
  372.    newnode(inherited, b, brother, "(nil)");
  373.  
  374. /*  transform lattice */
  375.    newdefnode(ntnode, mem, brother, transformlattice, 
  376.                    REPR(transformlattice));
  377.    if (prev_mem == nil) 
  378.       SON(alt) = brother;
  379.    else  
  380.       BROTHER(prev_mem) = brother;
  381.    prev_mem = brother;   
  382. }
  383.  
  384. /*  
  385.  *  add node "transform  lattice (>group,>"valLATTICE", T_%d.>).
  386.  */
  387.  
  388. add_lattice_term_to_afx_node(term,alt)
  389. int  term, alt;
  390. {
  391.    int b,mem ;
  392. /*  T_%d> */
  393.    REPR(term) = lattice_substitution_name;
  394.    newnode(affixnt, nil, nil, lattice_substitution_name);
  395.    newnode(derived, nil, brother, "(nil)");
  396.    b = brother;
  397. /*  LATTICE */
  398.    newnode(affixtm, nil, nil, lattice_val_repr);
  399.    newnode(inherited, b,brother, "(nil)");
  400.    b = brother;
  401. /*  >"groupnr" */
  402.    newnode(affixtm,  nil, nil, repr_group[group]);
  403.    newnode(inherited, b, brother, "(nil)");
  404.  
  405. /*  transform lattice */
  406.    newdefnode(ntnode, nil, brother, transformlatticeterm, 
  407.                    REPR(transformlatticeterm));
  408.  
  409.  mem = SON(alt);
  410.  if (mem  == nil) {
  411.       SON(alt) = brother;
  412.       return;
  413.  }
  414.  for  (; BROTHER(mem) != nil; mem = BROTHER(mem));
  415.  BROTHER (mem) = brother;
  416. }
  417.  
  418. /*  
  419.  *  insert  node "transform  lattice (>group,>"valLATTICE", T_%d.>).
  420.      after mem
  421.  */
  422.  
  423. insert_lattice_term_to_afx_node(term,mem,alt)
  424. int term, mem;
  425. {
  426.    int b ;
  427.    REPR(term) = lattice_substitution_name;
  428.  
  429. /*  T_%d> */
  430.    newnode(affixnt, nil, nil, lattice_substitution_name);
  431.    newnode(derived, nil, brother, "(nil)");
  432.    b = brother;
  433. /*  LATTICE */
  434.    newnode(affixtm, nil, nil, lattice_val_repr);
  435.    newnode(inherited, b,brother, "(nil)");
  436.    b = brother;
  437. /*  >"groupnr" */
  438.    newnode(affixtm,  nil, nil, repr_group[group]);
  439.    newnode(inherited, b, brother, "(nil)");
  440.  
  441. /*  transform lattice */
  442.    newdefnode(ntnode, mem, brother, transformlatticeterm, 
  443.                    REPR(transformlatticeterm));
  444.    if (prev_mem == nil) 
  445.       SON(alt) = brother;
  446.    else  
  447.       BROTHER(prev_mem) = brother;
  448.    prev_mem = brother;   
  449. }
  450.  
  451.  
  452. /* code part */
  453.  
  454. int    el_count; 
  455. conv_table() {
  456.    int ag ;
  457.    if (!MARKED(root,docompile)) {
  458.       fprintf(output,"struct char_ptr_list { char *l[32];};\n"); 
  459.       fprintf(output,"extern struct char_ptr_list groups[%d];\n",max_group); 
  460.       return;
  461.    }
  462.    group = -1;
  463.    fprintf(output,"struct char_ptr_list { char *l[32];};\n"); 
  464.    fprintf(output,"struct char_ptr_list groups[%d] = {\n",max_group); 
  465.    for ( ag = first_lattice ; ag != nil; ag = BROTHER(ag))
  466.      if (top_def(ag))  { 
  467.         fprintf(output,"{"); 
  468.         group  = DEF(ag);
  469.         top = ag;
  470.         count = 0;
  471.         el_count = 1;
  472.         code_group(ag);
  473.         if (el_count-1 != NODENAME(ag) )
  474.            fprintf(stderr,"glammar : lattice code generation error?\
  475.            ag = %x, el_count =%x\n",NODENAME(ag),el_count); 
  476.              
  477.         fprintf(output,"},\n"); 
  478.       }
  479.    fprintf(output,"};\n"); 
  480. }
  481.  
  482. int top_def(ag)  
  483. int ag;
  484. {
  485.   int g;
  486.   
  487.   for ( g = first_lattice; g != nil; g = BROTHER(g))
  488.      if (DEF(g) == DEF(ag))
  489.           return g == ag;
  490.   return false;
  491. }
  492. code_group(ag)
  493. int ag;
  494. {
  495.   int mem;
  496.   for (mem = SON(ag) ; mem != nil; mem = BROTHER(mem)) {
  497.     int def  = DEF(mem);
  498.     if ( def == -1) {
  499.       if  (el_count == NODENAME(mem))  {
  500.        el_count <<= 1;
  501.        code_lattice_el(mem);
  502.       }
  503.     }
  504.     else   
  505.       code_group(def);
  506.    }
  507. }
  508.  
  509.  
  510. code_lattice_el(mem)
  511. {
  512.    register int    ag,member;
  513.    register char * repr = REPR(mem);
  514.    for (ag = top;  ag != nil; ag = BROTHER(ag))
  515.       for (member = SON(ag); member != nil; member = BROTHER(member))  
  516.           if (mem == member) {
  517.              fprintf(output,"\"%s\",\n\t",repr);
  518.              return;
  519.            } else if (REPR(member) == repr)  {
  520.               fprintf(output,"\"%s\",\n\t",repr);
  521.               return;
  522.            }
  523.            
  524. }
  525.  
  526. /* 
  527.  * Need to know if a lattice term occuring in the lefthandside
  528.  * is used in the righthandside.
  529.  * If it is then we can use the name of the term;
  530.  * otherwise a terminal is made with its value converted 
  531.  * to decimal as the terminals value.
  532.  * Here we only make it a terminal; at code generation 
  533.  * the value of the lattice-term is known and filled in.
  534.  */
  535.  
  536. lattice_used(term, alt)
  537. int             term, alt;
  538. {
  539.    int             affix, mem, trm;
  540.  
  541.    for (mem = SON(alt); mem != nil; mem = BROTHER(mem)) {
  542.       for (affix = AFFIXTREE(mem); affix != nil; affix = BROTHER(affix))
  543.          if (LATTICE(affix)) {
  544.             trm = SON(affix);
  545.             if (REPR(trm) == REPR(term))
  546.                return;
  547.         }
  548.    }
  549.    NODENAME(term) = affixtm;
  550. }
  551.  
  552. int lattice_top(afx)
  553. {
  554.    register int    ag,def,n,r;
  555.    def = LATTICE_DEF(SON(afx));
  556.    n = DEF (def);
  557.    r =  NODENAME(def);
  558.    for (ag = first_lattice;  ag != nil; ag = BROTHER(ag))
  559.           if (DEF(ag) == n)
  560.             return NODENAME(ag) == r;
  561.    return false;
  562. }
  563.